package traverser;
/* The same algorithm with KeywordFirstTraversal. But this one uses multi-threads.
 * Author: Mark 
 * 
 */

public class KeywordConcurrentTraverser {
	KeyTracker tracker;
	String linkStart;
	String linkEnd;
	
	public static boolean ifFoundTargetLink=false;   //a flag showing if we find the target
	int threadNum;                //how many threads will be running
	public static long startTime;
	String[] linksVisited;         
	int currentVisitedNum;        //record the steps
	
	public KeywordConcurrentTraverser(String linkStart,String linkEnd,int threadNum){
		startTime=System.currentTimeMillis();
		this.linkStart=linkStart;
		this.linkEnd=linkEnd;
		this.threadNum=threadNum;
		
		System.out.println("Start: "+linkStart);
		linksVisited=new String[100];
		for(int i=0;i<100;i++){
			linksVisited[i]="";
		}
		Search();
		currentVisitedNum=0;
	}
	
	
	
	public void Search(){
		tracker = new KeyTracker(linkEnd, true);  //store the keyword of the end page as hashmap
		String nextLink = linkStart;
		linksVisited[currentVisitedNum++] = nextLink;
		while(ifFoundTargetLink == false){
			CacheLinkProcessor clp = new CacheLinkProcessor(nextLink);
			clp.removeDuplicates();
			String[] links = clp.getLinks();
			KeywordThread[] linkThread=new KeywordThread[threadNum];
			
			//Start all the threads
			for(int i=0;i<threadNum;i++){
				linkThread[i]=new KeywordThread(links, i, threadNum, tracker, linkEnd);
				linkThread[i].start();
			}
			
			try{
				long tempStart = System.currentTimeMillis();				
				for(int i=0;i<threadNum;i++){
					if(linkThread[i].interrupted()) {    //detect if any thread has interrupted
						ifFoundTargetLink=true;
					}
					linkThread[i].join();
				}
			}catch(Exception e){	
			}
			
			//if we haven't found the target link, we might need to choose the link with the highest priority as our next link
			if(ifFoundTargetLink == false) {
				int[] p= new int[threadNum];
				String[] nextLinks=new String[threadNum];
				//get the highest-priority links of each threads
				for(int i=0;i<threadNum;i++){
					p[i]=linkThread[i].getHighestPriority();
					nextLinks[i]=linkThread[i].getNextlink();
				}
				//sequence these links
				int highestPriority=0;
				for(int i=0;i<p.length;i++){
					for(int j=i+1;j<p.length;j++)
						if(p[i]<p[j]){
							int tempPri=p[j];
							String tempLink=nextLinks[j];
							p[j]=p[i];
							nextLinks[j]=nextLinks[i];
							p[i]=tempPri;
							nextLinks[i]=tempLink;
						}
				} 

				//choose the one with highest priority and not visited before
				int next=0;
				nextLink=nextLinks[next];
				highestPriority=p[next++];
				while(IfVisited(nextLink,linksVisited,currentVisitedNum)){
					nextLink=nextLinks[next];
					highestPriority=p[next++];
				}


				System.out.println("Visit "+nextLink+" with priority of "+highestPriority+"  "+(System.currentTimeMillis()-startTime));
				linksVisited[currentVisitedNum++]=nextLink;
			}
		}
		System.out.println("Found target link "+linkEnd+"  "+(System.currentTimeMillis()-startTime));
	}

	public boolean IfVisited(String link,String[] visitedLink,int visitedNum){
		boolean ifVisited=false;
		for(int i=visitedNum-1;i>=0;i--){
			if(link.equals(visitedLink[i])) ifVisited=true;
		}
		return ifVisited;
	}

	public static void main(String[] args){
		String link_start="http://en.wikipedia.org/wiki/The_Lord_of_the_Rings";
		String link_end="http://en.wikipedia.org/wiki/Turkish_Cypriots";
		final int threads=20;
		KeywordConcurrentTraverser k=new KeywordConcurrentTraverser(link_start, link_end, threads);

	}

}
